
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>
typedef int Qdatetype;
typedef struct QueueNode
{
	struct QueueNode* next;
	Qdatetype date;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;
}Queue;
void QueueInit(Queue* pd)
{
	assert(pd);
	pd->head = NULL;
	pd->tail = NULL;
	pd->size = 0;
}
void Queuepush(Queue* pd, Qdatetype x)
{
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	assert(newnode);
	newnode->date = x;
	newnode->next = NULL;
	if (pd->head == NULL)
	{
		pd->head = pd->tail = newnode;
	}
	else
	{
		pd->tail->next = newnode;
		pd->tail = newnode;
	}
	pd->size++;
}
void Queuedestroy(Queue* pd)
{
	assert(pd);
	QNode* cur = pd->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pd->head = pd->tail = NULL;
	pd->size = 0;
}
//
void Queuepop(Queue* pq)
{
	assert(pq);
	assert(pq->head != NULL);


	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}

	pq->size--;
}
Qdatetype Queuesize(Queue* pd)
{
	assert(pd);
	return pd->size;
}
bool Queueempty(Queue* pd)
{
	assert(pd);
	return pd->size == 0;

}
Qdatetype Queuefront(Queue* pd)
{
	assert(pd);
	assert(!Queueempty(pd));
	return pd->head->date;
}
Qdatetype Queueback(Queue* pd)
{
	assert(pd);
	return pd->tail->date;
}
typedef struct Mystack
{
	Queue q1;
	Queue q2;
}Mystack;

Mystack* Mystackcreate() {
	Mystack* pst = (Mystack*)malloc(sizeof(Mystack));
	QueueInit(&pst->q1);
	QueueInit(&pst->q2);
	return pst;
}
void Mystackpush(Mystack* obj,int x)
{
	if (!Queueempty(&obj->q1))
	{
		Queuepush(&obj->q1, x);
	}
	else
		Queuepush(&obj->q2,x);
}
int Mystackpop(Mystack* obj)
{
	Queue* pempty = &obj->q1;
	Queue* pnotempty = &obj->q2;
	if (Queueempty(&obj->q1)!=0)
	{
		pnotempty=&obj->q2;
		pempty=&obj->q1;
	}
	while (Queuesize(pnotempty) > 1)
	{
		Queuepush(pempty,Queuefront(pnotempty));
		Queuepop(pnotempty);
	}
	int top = Queuefront(pnotempty);
	Queuepop(pnotempty);
	return top;
}

int Mystackback(Mystack* obj)
{
	Queue* pempty = &obj->q1;
	Queue* pnotempty = &obj->q2;
	if (Queueempty(&obj->q1) != 0)
	{
		pnotempty = &obj->q2;
		pempty = &obj->q1;
	}
	return Queueback(pnotempty);
}
bool Mystackempty(Mystack* obj) {
	return (Queueempty(&obj->q1) && Queueempty(&obj->q2));
}
void Mystackdestroy(Mystack* obj)
{
	Queuedestroy(&obj->q1);
	Queuedestroy(&obj->q2);
	free(obj);
}
int Mystacktop(Mystack* obj)
{
	Queue* pempty = &obj->q1;
	Queue* pnotempty = &obj->q2;
	if (Queueempty(&obj->q1) != 0)
	{
		pnotempty = &obj->q2;
		pempty = &obj->q1;
	}
	return Queuefront(pnotempty);
}
int main()
{
	Mystack* pst = Mystackcreate();
	Mystackpush(pst, 1);
	Mystackpush(pst, 2);
	Mystackpush(pst, 3);
	Mystackpush(pst, 4);
	
	printf("%d", Mystacktop(pst));
	
	
	printf("%d", Mystackback(pst));
	
	return 0;
}